MIT 6.172 L3 Bit Hacks
课程主页：
课程视频：
https://www.bilibili.com/video/BV1wA411h7N7
这次回顾第三讲，这一讲介绍了位级的技巧。
Lecture 3 Bit Hacks
二进制表示
令
是$w$比特计算机单词。
如果$x$表示无符号整数，那么其对应的值为
如果$x$表示带符号整数，那么其对应的值为
特例：
考虑
x = 0b11...1那么
互补关系
因为我们有
x + ~x = -1所以可得
-x = ~x + 1设置第k个比特
y = x | (1 << k);清除第$k$个比特
y = x & ~(1 << k);翻转第k个比特
y = x ^ (1 << k);提取比特域
(x & mask) >> shift例子：
设置比特域
x = (x & ~mask) | (y << shift)不利用临时变量交换两数
x = x ^ y;
y = x ^ y;
x = x ^ y;原因：
(x ^ y) ^ y = x不使用分支计算最小值
r = y ^ ((x ^ y) & -(x < y));原因：
如果$ x<y$，那么
-(x < y) = 0b1...1
(x ^ y) & -(x < y) = (x ^ y)
r = y ^ (x ^ y) = x如果$x\ge y$，那么
-(x < y) = 0b0...0
(x ^ y) & -(x < y) = 0
r = y ^ 0 = y应用
对不可预测的分支，可以利用之前的方法进行优化：
条件1,2,4大多数情形都成立，所以称其为可预测的，条件3无法判断何时成立，对此处进行之前的优化：
static void merge(long * __restrict C,
long * __restrict A,
long * __restrict B,
size_t na,
size_t nb) {
while (na > 0 && nb > 0) {
long cmp = (*A <= *B);
long min = *B ^ ((*B ^ *A) & (-cmp));
*C++ = min;
A += cmp; na -= cmp;
B += !cmp; nb -= !cmp;
}
while (na > 0){
*C++ = *A++;
na--;
}
while (nb > 0){
*C++ = *B++;
nb--;
}
}模加法
假设我们计算
我们假设
优化方式如下：
z = x + y;
r = z - (n & -(z >= n));向上近似到$2$的幂
计算
实际上只要找到为$1$的最高位即可，方式如下：
uint64_t n;
--n;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
++n;效果：
一开始让$n$减$1$是为了处理$n=2^k$的情形。
备注：此处
最低有效位的1
方法如下：
r = x & (-x)例子：
计算$\lg x$，其中$x$为$2$的幂
方法如下：
原因如下：
长度为$2^k$的deBruijn序列$s$是0-1循环序列，使得长度为$k$的$2^k$个0-1串中作为$s$的子串恰好出现一次。
考虑$k=3$：
原因：
https://www.cnblogs.com/shangdawei/p/3967505.html
N皇后问题的比特向量表示
利用比特表示放置情况，比特位为$1$表示放置了queen。
在$c$列中放置queen是不安全的，如果下式非零：
down & (1 << c)
其中down的第$k$位为$1$，当且仅当第$k$列放置了queen。
其中left是长度为$2n-1$的比特数组，left的第$k$位为$1$，当且仅当第$k$个对角线上放置了queen，所以判断条件为：
left & (1 << (r + c))
同理right数组存储副对角线，判断条件为：
right & (1 << (n - 1 - r + c))计算$x$的比特表示中$1$的个数
方法1：
for (r=0; x!=0; ++r)
x & = x - 1;该操作每次消除最低有效位的$1$：
方法2：
static const int count[256]=
{ 0, 1, 1, 2, 1, 2, 2, 3, 1, …, 8};
for (int r = 0; x !=0; x >>= 8)
r += count[x & OxFF];思路是预先计算所有$8$比特数所含$1$的个数。
方法3：
Compute popcount的前两步是为了防止溢出。
计算流程：
原因解释：
第一步操作计算每两个位置中$1$的个数：
x = ((x >> 1) & M0) + (x & M0)第二步操作计算了每四个位置中$1$的个数：
x = ((x >> 2) & M1) + (x & M1)其余操作以此类推。。。
内置函数：
int builtin_popcount (unsigned int x);